package com.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/5/26 15:07
 * @description 快排
 */
public class QuickSortDemo {

    public static void main(String[] args) {
        int[] ints = {3, 2, 1, 2, 5, 6, 7, 8, 1, 4, 5, 6};
        quickSort(ints, 0, ints.length - 1);
        System.out.println(Arrays.toString(ints));
    }


    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //未经优化过的快排的最差时间复杂度是O(n^2) 因为我们每次都会选择一个基准值作为排序基准 默认使用最后一个元素
            //但是最后一个元素他可能是一个极值 如果它是一个极值 那么快排就会退化为O(n^2)的时间复杂度  因为它每次只处理一个元素
            //我们使用一个随机算法 从l到r-1的位置随机找一个数字取替换掉right的那个值
            swap(arr, left + new Random().nextInt(right - left + 1), right);

            //荷兰国旗2会将相等元素放到中间 这个partition函数就是帮助我们获取到每次相等元素的左右边界
            int[] p = partition(arr, left, right);//这是去得到每次分区后的左右边界

            quickSort(arr, left, p[0] - 1);//继续快排左边界
            quickSort(arr, p[1] + 1, right);//继续快排右边界
        }
    }

    private static int[] partition(int[] arr, int left, int right) {
        //基本和荷兰国旗2的写法一样 需要一个左边界和一个右边界
        int less = left - 1;//左边界
        int more = right;//右边界
        //如果左边界碰撞到右边界时结束循环
        while (left < more) {
            if (arr[left] < arr[right]) {
                //如果当前的数字小于基准值
                swap(arr, ++less, left++);//将左边界的前一个数字设置为它 并且左边界前进一步 当前指针位置也要前进一步
            } else if (arr[left] > arr[right]) {
                //如果当前数字大于基准值
                swap(arr, --more, left);//将右边界的前一个数字设置为它 并且右边界后退一步 当前指针位置不变
            } else {
                left++;//等于往前走就好
            }
        }
        swap(arr, more, right);
        return new int[]{less + 1, more};
    }

    public static void swap(int[] arr, int i, int j) {
        //涉及到自己和自己交换 我们不能使用异或
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
